One issue that is important when scheduling batch jobs is guaranteeing that jobs are completed by an expected deadline. In particular, service level agreements may need to be met for specific jobs or groups of jobs. “Critical path analysis” may be used to analyze batch job dependencies to identify the most critical path to achieve an expected deadline. In general, critical path analysis may involve breaking a task (e.g., a sequence of jobs) into a series of related activities (e.g., jobs). The success or failure of the task depends on the management and scheduling of the activities. In particular, information on likely activity duration, cost, and logically necessary operations may be used to optimize the performance of the task.
For a given task, some activities may depend on others. In particular, some activities may only begin when other activities (known as predecessor activities or jobs) have been completed. Other activities may take place concurrently and a task may only be complete when all the activities have been completed. Some activities in the task may be critical. In such cases, if these activities are delayed, completion of the task may also be delayed. Similarly, other activities may be non-critical, meaning that they can be delayed some amount without delaying the entire task.
A scheduling product may need to monitor critical jobs and prioritize them and their predecessors in such a way that the deadlines for service level agreement jobs are satisfied. However, one significant problem in achieving this end is optimizing resource usage. For example, prioritizing all the predecessor jobs of a critical job would be tantamount to having no prioritization. Thus, it may be necessary to identify a subset of predecessor jobs to monitor and prioritize.
A critical path (i.e., a sequence of predecessor jobs that, if delayed, can cause delay of a dependent critical job) may be calculated statically before a work flow execution begins. In practice, a critical path may be calculated by starting from a critical job, and regressing backward through a chain of predecessor jobs. However, there are several conditions that may render a critical path invalid at execution time. For example, a “most critical predecessor” job may be determined by evaluating estimated data that may produce unrealistic results. For example, an estimated job duration may be calculated based on historical data, but a particular run of a job may be longer than usual. Similarly, a user may need to change a plan, for example, by reducing available resources or adding a new job. This could cause another predecessor job to be more critical than a job believed to be the most critical at planning time. Or there could simply be more than one path that is critical to complete a job.